#include <bits/stdc++.h>
using namespace std;

/*
1394. 找出数组中的幸运数
已解答
简单
相关标签
premium lock icon
相关企业
提示
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

如果数组中存在多个幸运数，只需返回 最大 的那个。
如果数组中不含幸运数，则返回 -1 。
 

示例 1：

输入：arr = [2,2,3,4]
输出：2
解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
示例 2：

输入：arr = [1,2,2,3,3,3]
输出：3
解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
示例 3：

输入：arr = [2,2,2,3,3]
输出：-1
解释：数组中不存在幸运数。
示例 4：

输入：arr = [5]
输出：-1
示例 5：

输入：arr = [7,7,7,7,7,7,7]
输出：7
 

提示：

1 <= arr.length <= 500
1 <= arr[i] <= 500
*/

// 法一
class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr)     freq[num]++;

        int maxLucky = -1;
        // 遍历哈希表，查找所有数值等于其出现次数的元素
        for (const auto& pair : freq) {
            // 数值等于其出现次数
            if (pair.first == pair.second)
                maxLucky = max(maxLucky, pair.first);  //  更新最大幸运数
        }
        return maxLucky;
    }
};

// 法二
class Solution {
public:
    int findLucky(vector<int>& arr) {
        // 利用题目约束：数组元素范围为1到500
        constexpr size_t LEN = 501;
        // 使用静态数组统计频率，初始化为全0
        array<int, LEN> freq{};

        // 统计每个数值的出现次数
        for (int num : arr) {
            freq[num]++;
        }

        // 逆序遍历数组，优先检查较大的数值
        for (int i = LEN - 1; i > 0; i--) {
            // 若当前数值等于其出现次数，则为最大幸运数
            if (freq[i] == i) {
                return i;
            }
        }

        // 未找到符合条件的幸运数
        return -1;
    }
};